#include <iostream>
#include <queue>
#include <stack>

using namespace std;
typedef struct BinaryTree {
    int data;
    struct BinaryTree *left;
    struct BinaryTree *right;

} BinaryTree;

void createBinaryTree(BinaryTree *&root) {
    root = nullptr;
    int num;
    cin >> num;
    if (num != -1) {
        root = (BinaryTree *) malloc(sizeof(BinaryTree));
        root->left = nullptr;
        root->right = nullptr;
        root->data = num;
        createBinaryTree(root->left);
        createBinaryTree(root->right);
        return;
    }

};

void preorder(BinaryTree *root) {
    if (root) {
        cout << root->data << " ";
        preorder(root->left);
        preorder(root->right);
    }
}

void layerorder(BinaryTree *root) {
    queue<BinaryTree *> q;
    if (root) {
        q.push(root);
    }
    while (!q.empty()) {
        BinaryTree *f = q.front();
        q.pop();
        cout << f->data << " ";
        if (f->left)
            q.push(f->left);
        if (f->right)
            q.push(f->right);
    }
}

//自上而下自左向右遍历
void YouZuoGen(BinaryTree *root) {
    if (root) {
        YouZuoGen(root->right);
        YouZuoGen(root->left);
        cout << root->data << " ";
    }
}

//后续非递归遍历
void postorder_NoRecur(BinaryTree *root) {
    stack<BinaryTree *> s;
    BinaryTree *p = root;
    BinaryTree *pre = NULL;
    while (!s.empty() || p) {
        while (p) {
            s.push(p);
            p = p->left;
        }

        BinaryTree *top = s.top();
        s.pop();
        if (top->right != NULL && pre != top->right) {
            s.push(top);
            p = top->right;
        } else {
            cout << top->data << " ";
            pre = top;
        }

    }

}

//中序非递归遍历
void inorder_NoRecur(BinaryTree *root) {
    stack<BinaryTree *> s;
    BinaryTree *p = root;
    while (!s.empty() || p) {
        while (p) {
            s.push(p);
            p = p->left;
        }
        BinaryTree *top = s.top();
        s.pop();
        cout << top->data << " ";
        p = top->right;

    }
}

//前序非递归遍历
void preorder_Norecur(BinaryTree *root) {
    stack<BinaryTree *> s;
    BinaryTree *p = root;
    while (!s.empty() || p) {
        while (p) {
            cout << p->data << " ";
            s.push(p);
            p = p->left;
        }
        BinaryTree *top = s.top();
        s.pop();
        p = top->right;

    }
}

//求二叉树某个结点的高度
int getHeight(BinaryTree *root) {
    if (!root) {
        return 0;
    }
    return max(getHeight(root->left), getHeight(root->right)) + 1;
}


//判断平衡二叉树
bool IsBalanceTree(BinaryTree *root) {
    if (root == NULL) {
        return true;
    } else {
        if (abs(getHeight(root->left) - getHeight(root->right)) <= 1) {
            return IsBalanceTree(root->left) && IsBalanceTree(root->right);
        } else
            return false;
    }
}


//广度遍历计算树的高度
int layerorderGetHeight(BinaryTree *root) {
    queue<BinaryTree *> q;
    if (root) {
        q.push(root);
    } else
        return 0;
    int layer = 0;//层次
    while (!q.empty()) {
        //每次只要算了cnt就一定有层次 算一次加1
        int cnt = q.size();//获取当前队列内元素个数 表示该层次元素的个数
        layer++;
        while (cnt--) {
            BinaryTree *f = q.front();

            q.pop();
            if (f->left)
                q.push(f->left);
            if (f->right)
                q.push(f->right);
        }

    }
    //如果都遍历完了还没找到
    return layer;

}


//广度遍历判断某一点在第几层
int layerorderFindNode(BinaryTree *root, int data) {
    queue<BinaryTree *> q;
    if (root) {
        q.push(root);
    }
    int layer = 0;//层次
    while (!q.empty()) {
        int cnt = q.size();//获取当前队列内元素个数 表示该层次元素的个数
        layer++;
        while (cnt--) {
            BinaryTree *f = q.front();
            if (data == f->data)  //如果找到直接返回层次
            {
                return layer;
            }

            q.pop();
            if (f->left)
                q.push(f->left);
            if (f->right)
                q.push(f->right);
        }

    }
    //如果都遍历完了还没找到
    return -1;

}

//广度遍历判断是否是完全二叉树
bool IsCompleteTree(BinaryTree *root) {
    queue<BinaryTree *> q;
    if (root) {
        q.push(root);
    } else
        return 0;
    BinaryTree* f=NULL;
    while(f=q.front())
    {
        q.pop();
        q.push(f->left);
        q.push(f->right);
    }
    //空的时候退出
    //此时队列里面应该都是空元素
    while(!q.empty())
    {
        BinaryTree* front=q.front();
        if(front)
            return false;
        q.pop();
    }
    return true;


}

//根据数组递归建树
//必定有中序

//前序和中序
BinaryTree * createBinaryTree(int pre[],int preLeft,int preRight,int in[],int inLeft,int inRight)
{
    if(preLeft>preRight)
        return NULL;
    BinaryTree * root=new BinaryTree;
    root->data=pre[preLeft];
    root->left=NULL;
    root->right=NULL;
    int k=-1;
    for(int i=inLeft;i<=inRight;++i)
    {
        if(root->data==in[i])
        {
            k=i;
            break;
        }
    }
    root->left=createBinaryTree(pre,preLeft+1,k-inLeft+preLeft,in,inLeft,k-1);
    root->right=createBinaryTree(pre,k-inLeft+preLeft+1,preRight,in,k+1,inRight);
    return root;
    //左子树  pre (preLeft+1,k-inLeft+preLeft)        in (inLeft,k-1)
    //右子树  pre   (k-inLeft+preLeft+1,preRight)     in (k+1,inRight)
    //找到根结点的位置划分左右子树
}

//中序和后序
BinaryTree * createBinaryTreePost(int post[],int postLeft,int postRight,int in[],int inLeft,int inRight)
{
    if(postLeft>postRight)
        return NULL;
    BinaryTree * root=new BinaryTree;
    root->data=post[postRight];
    root->left=NULL;
    root->right=NULL;
    int k=-1;
    for(int i=inLeft;i<=inRight;++i)
    {
        if(root->data==in[i])
        {
            k=i;
            break;
        }
    }
    root->left=createBinaryTree(post,postLeft,postRight+k-inRight-1,in,inLeft,k-1);
    root->right=createBinaryTree(post,postRight+k-inRight,postRight-1,in,k+1,inRight);
    return root;
    //左子树  post (postLeft,postRight+k-inRight-1)        in (inLeft,k-1)
    //右子树  post   (postRight+k-inRight,postRight-1)     in (k+1,inRight)
    //找到根结点的位置划分左右子树
}

//交换二叉树的左右子树
void changeBinaryTree(BinaryTree* root)
{
    if(root)
    {
        BinaryTree * temp=root->left;
        root->left=root->right;
        root->right=temp;
        changeBinaryTree(root->left);
        changeBinaryTree(root->right);
    }
}

//删除二叉树中以某个x为根的子树
//从root开始递归删除
void deleteX(BinaryTree* root)
{
    if(root)
    {
        deleteX(root->left);
        deleteX(root->right);
        free(root);
    }
}
//思路：通过树的层次遍历  找到要删除结点的父结点将其子结点递归删除
void DeleteXByLayerOrder(BinaryTree * root,int x) {
    queue<BinaryTree *> q;
    if (root) {
       q.push(root);
    }
    while (!q.empty()) {
        BinaryTree *f = q.front();
        q.pop();
        if(f->left->data==x)
        {
           deleteX(f->left);
           f->left=NULL;
        }
        else if(f->right->data==x)
        {
            deleteX(f->right);
            f->right=NULL;
        }
        else
        {
            if (f->left)
                q.push(f->left);
            if (f->right)
                q.push(f->right);
        }

    }
}



//寻找二叉树中2个结点的最近公共祖先




//寻找x并打印x的所有祖先结点
void postorder_NoRecurPrintXAncestor(BinaryTree* root,int x)
{
    stack<BinaryTree*>s;
    BinaryTree* pre=nullptr;
    BinaryTree* p=root;
    while(p||!s.empty())
    {
        while(p)
        {
            s.push(p);
            p=p->left;
        }
        BinaryTree* top=s.top();
        s.pop();

        if(top->data==x)
        {
            while(!s.empty())
            {
                cout<<s.top()->data<<" ";
                s.pop();
            }
        }
        if(top->right&&pre!=top->right)
        {
            s.push(top);
            p=top->right;
        }else
        {
          //什么也不做
        }

    }
}


//查找二叉树结点的公共父节点
//递归方法求解



//后序非递归求祖先 比较两个数组


//前序遍历记录到某一点的路径

//
//BinaryTree *LeastCommonAncestor(BinaryTree* root,BinaryTree* p,BinaryTree* q)
//{
//    vector<BinaryTree*>v1=postorder_NoRecurPrintXAncestor(root,p)
//    vector<BinaryTree*>v2=postorder_NoRecurPrintXAncestor(root,q)
//    int res=-1;
//    //找出v1和v2从前到后相等的最后一个位置
//    for(int i=0;i<min(v1.size(),v2.size());++i)
//    {
//        if(v1[i]==v2[i])
//             res=i;
//    }
//    if(res==-1)
//        return nullptr;
//    else
//        return v1[res];
//
//}
//if (root == null) {
//return null;
//}
//if (root == p || root == q) {
//return root;
//}
//TreeNode left = lowestCommonAncestor(root.left, p, q);
//TreeNode right = lowestCommonAncestor(root.right, p, q);
//if (left != null && right != null) {
//// p q 一个在左，一个在右
//return root;
//}
//if (left != null) {
//// p q 都在左子树
//return left;
//}
//if (right != null) {
//// p q 都在右子树
//return right;
//}

int main() {

    BinaryTree *root = nullptr;


    //前序中序建立二叉树
/*
    int pre[1000];
    int in[1000];
    int n;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>pre[i];
    }
    for(int i=0;i<n;++i)
    {
        cin>>in[i];
    }
    root=createBinaryTree(pre,0,n-1,in,0,n-1);
    layerorder(root);*/


    //后序序中序建立二叉树
/*    int post[1000];
    int in[1000];
    int n;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>post[i];
    }
    for(int i=0;i<n;++i)
    {
        cin>>in[i];
    }
    root=createBinaryTreePost(post,0,n-1,in,0,n-1);
    layerorder(root);*/




    createBinaryTree(root);
//    preorder(root);
//    layerorder(root);
//    YouZuoGen(root);
//    postorder_NoRecur(root);
//    inorder_NoRecur(root);
//    preorder_Norecur(root);
//    cout << getHeight(root);
//    cout << IsBalanceTree(root);
//    cout << layerorderFindNode(root, 4);
//    cout << layerorderGetHeight(root);
//    cout << IsCompleteTree(root);

//    DeleteXByLayerOrder(root,2);
//    layerorder(root);
//     postorder_NoRecurPrintXAncestor(root,5);


    return 0;
}


//public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//    if (root == null) {
//        return null;
//    }
//    if (root == p || root == q) {
//        return root;
//    }
//    TreeNode left = lowestCommonAncestor(root.left, p, q);
//    TreeNode right = lowestCommonAncestor(root.right, p, q);
//    if (left != null && right != null) {
//        // p q 一个在左，一个在右
//        return root;
//    }
//    if (left != null) {
//        // p q 都在左子树
//        return left;
//    }
//    if (right != null) {
//        // p q 都在右子树
//        return right;
//    }
//    return null;
//}